

package graph


import "container/list";
import "container/vector";  





type ColorMap struct {
    m map[Vertex] Color;
    
    // Default color to return when vertex is not in the map.
    defaultColor Color;
}

func (self ColorMap) Color(v Vertex) Color {
    color,present := self.m[v];
    if !present {
        color = self.defaultColor;
    } 
    return color;
}

func (self ColorMap) SetWhite(v Vertex) {
    self.m[v] = WHITE;
}

func (self ColorMap) SetGrey(v Vertex) {
    self.m[v] = GREY;
}

func (self ColorMap) SetBlack(v Vertex) {
    self.m[v] = BLACK;
}


func BFS(g *Graph, s Vertex, 
    discover_vertex func(Vertex), 
    finish_vertex func(Vertex), 
    process_edge func(*Edge, ColorMap)) 
{
    queue := list.New();
    queue.PushBack(s);
    colorMap := ColorMap{make(map[Vertex] Color), WHITE};
    colorMap.SetWhite(s);
    for {
        if queue.Len() == 0 {
            break;
        }
        vEl := queue.Front();
        queue.Remove(vEl);
        v := vEl.Value;
        discover_vertex(v);
        edgeIter := g.OutEdges(v);
        for !edgeIter.End() {
            e := edgeIter.Next();
            u := e.Dest();
            color := colorMap.Color(u);
            if color != BLACK || g.Directed() {
                process_edge(e.(*Edge), colorMap);
            }
            if color == WHITE {
                queue.PushBack(u);
                colorMap.SetGrey(u);
            }
        }
        finish_vertex(v);
        colorMap.SetBlack(v);
    } 
}




type DFSVisitor interface {
    DiscoverVertex(Vertex);
    FinishVertex(Vertex);
    ExamineEdge(*Edge);
    ExamineTreeEdge(*Edge);
    ExamineBackEdge(*Edge);
    ExamineCrossOrForwardEdge(*Edge);
}



type timestamp struct {
    DiscoverTime int;
    FinishTime int;
}

type DFSTimeVisitor struct {
    timeMap map[Vertex] timestamp;
    time int;
}

func (DFSTimeVisitor) ExamineEdge(*Edge) {}
func (DFSTimeVisitor) ExamineTreeEdge(*Edge) {}
func (DFSTimeVisitor) ExamineBackEdge(*Edge) {}
func (DFSTimeVisitor) ExamineCrossOrForwardEdge(*Edge) {}

func (self DFSTimeVisitor) DiscoverVertex(v Vertex) {
    self.timeMap[v] = timestamp{self.time, 0};
    self.time++; 
}

func (self DFSTimeVisitor) FinishVertex(v Vertex) {
    var tm timestamp = self.timeMap[v];
    tm.FinishTime = self.time;
    self.time++;
}





func DFS(g *Graph, vis DFSVisitor) {
    colorMap := ColorMap{make(map[Vertex] Color), WHITE};
    vertexIter := g.Vertices();
    for !vertexIter.End() {
        v := vertexIter.Next();
        if colorMap.Color(v) == WHITE {
            dfsVisit(g, v, &colorMap, vis);
        }
    }
}


func DFSFromVertex(g *Graph, s Vertex, vis DFSVisitor) {
    
    colorMap := ColorMap{make(map[Vertex] Color), WHITE};
    colorMap.SetWhite(s);         
    dfsVisit(g, s, &colorMap, vis);
}

func dfsVisit(g *Graph, v Vertex, c *ColorMap, vis DFSVisitor) {
    vis.DiscoverVertex(v);
    c.SetGrey(v);
    edgeIter := g.OutEdges(v);
    for !edgeIter.End() {
        e := edgeIter.Next().(*Edge);
        vis.ExamineEdge(e);
        color := c.Color(e.Dest());
        if color == WHITE {
            vis.ExamineTreeEdge(e);
            dfsVisit(g, e.Dest(), c, vis);
        } else if color == GREY {
            vis.ExamineBackEdge(e);
        } else {
            vis.ExamineCrossOrForwardEdge(e);
        }
    }
    vis.FinishVertex(v);
    c.SetGrey(v);
}


func StrongComponents(g *Graph) (*vector.Vector) {
     return vector.New(0);
}
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
         